package org.example.algorithm.array;

import java.util.LinkedList;
import java.util.Queue;

public class RotateSolution {

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7};
        int k = 3;
        RotateSolution solution = new RotateSolution();
        solution.rotate3(nums, k);
        for (int i=0;i<nums.length;i++) {
            System.out.println(nums[i]);
        }
    }
    //三次翻转
    public void rotate(int[] nums, int k) {
        reverse(nums, 0, nums.length-1);
        reverse(nums, 0, k % nums.length - 1);
        reverse(nums, k % nums.length, nums.length-1);
    }

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

    //时间复杂度：O(n)
    //空间复杂度：O(n)
    public void rotate1(int[] nums, int k) {
        int len = nums.length;
        int needRotate = k % len;
        if (needRotate == 0) {
            return;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i=len-needRotate;i<2*len-needRotate;i++) {
            queue.offer(nums[i % len]);
        }
        for (int i=0;i<len;i++) {
            nums[i] = queue.poll();
        }
    }

    //部分用例超时
    public void rotate2(int[] nums, int k) {
        int len = nums.length;
        int needRotate = k % len;
        if (needRotate == 0) {
            return;
        }
        for (int i=len-needRotate;i<len;i++) {
            for (int j=i-1;j>=i-(len-needRotate);j--) {
                swap(nums, j, j+1);
            }
        }
    }

    //环状替换
    public void rotate3(int[] nums, int k) {
        int len = nums.length;
        int needRotate = k % len;
        if (needRotate == 0) {
            return;
        }
        //执行交换次数
        int count = 0;
        for (int i=0;i<len && count < len;i++) {
            int nextPos = i;
            int preValue = nums[i];
            do {
                nextPos = (nextPos + needRotate) % len;
                int temp = nums[nextPos];
                nums[nextPos] = preValue;
                //preValue记录上一个位置的值
                preValue = temp;
                count++;
            } while (nextPos != i);
        }
    }

    private void swap(int[] nums, int from, int to) {
        int temp = nums[from];
        nums[from] = nums[to];
        nums[to] = temp;
    }
}
